Những người nhập cư Trung Quốc đầu tiên đến Quần đảo Mã Lai từ tỉnh Quảng Đông và Phúc Kiến vào thế kỉ X TCN. Con số này bắt đầu tăng lên cực nhanh từ thế kỉ XV đến thế kỉ XVII, bởi những người tùy tùng đi theo một công chúa thời nhà Minh đến định cư khiến cho Trung Quốc trở thành một đối tác thương mại quan trọng của Malaysia.

Vào thế kỉ XV, một số thành quốc phải nộp cống cho các vương quốc khác như Trung Quốc và Xiêm. Nhưng mối quan hệ thương mại đã được mở ra vào thời đại Parameswara, đầu thế kỉ XV khi một đô đốc là một tín đồ Hồi Giáo người Trung Quốc tên là Trịnh Hòa, đã ghé thăm Malacca và Java khi đang trên một cuộc thám hiểm của mình (1405-1433). Theo một truyền thuyết, vào năm 1459 TCN, một vị hoàng đế Trung Quốc đã gửi một công chúa tên là Hang Li Po cùng với một số đoàn tùy tùng đi theo công chúa để phục tùng đến Malaysia để tỏ lòng tôn kính đối với Sultan. Ban đầu, họ định cư ở Bukit Cina và về sau họ trở thành những Peranakan.